//接雨水
class Solution {
public:
    int trap(vector<int>& height) 
    {
        //单调栈 升序栈 这样可以保证当我遇见一个比我高的柱子时
        //可以快速获得上一个比我高的柱子，从而进行计算
        stack<int>st;
        int res=0;
        st.push(0);
        for(int i=1;i<height.size();i++)
        {
            if(height[i] < height[st.top()])
            {
                st.push(i);
            }
            else if(height[i]==height[st.top()])
            {
                //因为一样高的时候 只需要找最靠近右边的那个就可以了
                st.pop();
                st.push(i);
            }
            else
            {
                while(!st.empty()&& height[i]>height[st.top()])
                {
                    int mid=st.top();
                    st.pop();
                    if(!st.empty())
                    {
                        int d=i-st.top()-1;
                        int h=min(height[st.top()],height[i])-height[mid];
                        res+=(d*h);
                    }
                }
                st.push(i);
            }

        }
        return res;
    }
};
//最小路径和
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int i=1;i<n;i++)
        {
            dp[0][i]=dp[0][i-1]+grid[0][i];
        }
        for(int j=1;j<m;j++)
        {
            dp[j][0]=dp[j-1][0]+grid[j][0];
        }
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};
//全排列
class Solution {
public:
    vector<vector<int>> res;
    vector<int>tmp;
    vector<vector<int>> permute(vector<int>& nums) 
    {
        if(nums.size()==0) return res;
        //注意这里是全排列 是没有当前下标的 每次都需要从头开始判断
        vector<bool>used(nums.size(),false);
        dfs(nums,used);
        return res;
    }
    void dfs(vector<int>& nums,vector<bool>& used)
    {
        if(tmp.size()==nums.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(used[i]) continue;
            used[i]=true;
            tmp.push_back(nums[i]);
            dfs(nums,used);
            tmp.pop_back();
            used[i]=false;
            
        }
    }
};

//搜索旋转排序数组
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            //查找旋转的节点
            int mid=(l+r+1)/2;
            if(nums[mid]>=nums[0])l=mid;
            else r=mid-1;
        }
        //分成了两个区间 [0,r] [r+1,end()]
        if(target>=nums[0])
        {
            //target在前面的区间
            l=0;
        }
        else
        {
            //在后面的区间
            l=l+1;
            r=nums.size()-1;
        }
        while(l<r)
        {
            int mid=(l+r)/2;
            if(nums[mid]>=target) r=mid;
            else l=mid+1;
        }
        if(nums[r]!=target) return -1;
        else return l;
    }
}